package com.example.leetcode.sort;

import java.util.*;

/**
 * @ClassName Solution_451
 * @Description TODO
 * @Author liuzhihui
 * @Date 28/4/2021 下午 10:52
 * @Version 1.0
 **/
public class Solution_451 {
    public static void main(String[] args) {
        String s = "tree";
        System.out.println(frequencySort(s));
    }
    public static String frequencySort(String s) {
        char[] c = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();

        // 统计字符出现次数
        for(int i = 0; i < c.length; i++){
            map.put(c[i], map.getOrDefault(c[i], 0) + 1);
        }

        // 定义优先列队
        Queue<Character> queue = new PriorityQueue<>((o1, o2) -> map.get(o2) - map.get(o1));

        // 统计的字符按照规则放进优先队列
        Set<Character> characters = map.keySet();
        for (Character character : characters) {
            queue.offer(character);
        }

        // 将优先队列的元素导出到结果集中
        char[] result = new char[s.length()];
        int index = 0;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Character character = queue.poll();
            int count = map.get(character);
            for (int i1 = 0; i1 < count; i1++) {
                result[index++] = character;
            }
        }
        return new String(result);
    }
}
